import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

        public List<List<Integer>> fourSum(int[] nums, int target) {

            List<List<Integer>> ret = new ArrayList();

            //1.排序
            Arrays.sort(nums);
            int n = nums.length;
            for (int i = 0; i < n; ) {
                //1.固定数a
                for (int j = i+1; j < n; ) {
                    //固定数b
                    int left = j + 1,right = n - 1;

                    int area = target - nums[i] - nums[j];
                    while (left < right){
                        int sum = nums[left] + nums[right];
                        //利用双指针解决问题
                        if (sum > area) {
                            right--;
                        }else if (sum < area) {
                            left++;
                        }else {
                            //添加进数组
                            ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                            //去重
                            left++;
                            right--;
                            while (left < right && nums[left] == nums[left - 1])left++;
                            while (left < right && nums[right] == nums[right + 1])right--;
                        }
                    }
                    //去重b
                    j++;
                    while (j < n && nums[j] == nums[j - 1])j++;
                }
                //去重a
                i++;
                while (i <n && nums[i] == nums[i - 1])i++;
            }
            return ret;

        }

    public static void main(String[] args) {
        Solution alg1 = new Solution();
        int[] arrys = {-2,-1,0,0,1,2,4,4,-4,8};
        List<List<Integer>> eas = alg1.fourSum(arrys,0);
        System.out.println(eas);
    }
    }

